using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStar
{
    /// <summary>
    /// 为房间构建一个路径，从 startGridPosition 到 endGridPosition，然后添加
    /// 移动到返回的堆栈。如果未找到路径，则返回 null。
    /// </summary>
    public static Stack<Vector3> BuildPath(Room room, Vector3Int startGridPosition, Vector3Int endGridPosition)
    {
        // 按下限调整位置
        startGridPosition -= (Vector3Int)room.templateLowerBounds;
        ;
        endGridPosition -= (Vector3Int)room.templateLowerBounds;

        // 创建开放列表和封闭哈希集
        List<Node> openNodeList = new List<Node>();
        HashSet<Node> closedNodeHashSet = new HashSet<Node>();

        // 创建用于路径查找的网格节点
        GridNodes gridNodes = new GridNodes(room.templateUpperBounds.x - room.templateLowerBounds.x + 1,
            room.templateUpperBounds.y - room.templateLowerBounds.y + 1);

        Node startNode = gridNodes.GetGridNode(startGridPosition.x, startGridPosition.y);
        Node targetNode = gridNodes.GetGridNode(endGridPosition.x, endGridPosition.y);

        Node endPathNode = FindShortestPath(startNode, targetNode, gridNodes, openNodeList, closedNodeHashSet,
            room.instantiatedRoom);

        if (endPathNode != null)
        {
            return CreatePathStack(endPathNode, room);
        }

        return null;
    }

    /// <summary>
    /// 查找最短路径 - 如果已找到路径，则返回结束节点，否则返回 null。
    /// </summary>
    private static Node FindShortestPath(Node startNode, Node targetNode, GridNodes gridNodes, List<Node> openNodeList,
        HashSet<Node> closedNodeHashSet, InstantiatedRoom instantiatedRoom)
    {
        // 将启动节点添加到打开列表
        openNodeList.Add(startNode);

        // 遍历打开的节点列表，直到为空
        while (openNodeList.Count > 0)
        {
            // 排序列表
            openNodeList.Sort();

            // 当前节点 = 打开列表中 fCost 最低的节点
            Node currentNode = openNodeList[0];
            openNodeList.RemoveAt(0);

            // 如果当前节点 = 目标节点，则完成
            if (currentNode == targetNode)
            {
                return currentNode;
            }

            // 将当前节点添加到已关闭的列表中
            closedNodeHashSet.Add(currentNode);

            // 评估当前节点的每个邻居的 FCOST
            EvaluateCurrentNodeNeighbours(currentNode, targetNode, gridNodes, openNodeList, closedNodeHashSet,
                instantiatedRoom);
        }

        return null;
    }

    /// <summary>
    ///  创建一个<Vector3>包含移动路径的堆栈
    /// </summary>
    private static Stack<Vector3> CreatePathStack(Node targetNode, Room room)
    {
        Stack<Vector3> movementPathStack = new Stack<Vector3>();

        Node nextNode = targetNode;

        // 获取单元格的中点
        Vector3 cellMidPoint = room.instantiatedRoom.grid.cellSize * 0.5f;
        cellMidPoint.z = 0f;

        while (nextNode != null)
        {
            // 将网格位置转换为世界位置
            Vector3 worldPosition = room.instantiatedRoom.grid.CellToWorld(new Vector3Int(
                nextNode.gridPosition.x + room.templateLowerBounds.x,
                nextNode.gridPosition.y + room.templateLowerBounds.y, 0));

            // 将世界位置设置为网格单元的中间位置
            worldPosition += cellMidPoint;

            movementPathStack.Push(worldPosition);

            nextNode = nextNode.parentNode;
        }

        return movementPathStack;
    }

    /// <summary>
    /// 评估邻居节点
    /// </summary>
    private static void EvaluateCurrentNodeNeighbours(Node currentNode, Node targetNode, GridNodes gridNodes,
        List<Node> openNodeList, HashSet<Node> closedNodeHashSet, InstantiatedRoom instantiatedRoom)
    {
        Vector2Int currentNodeGridPosition = currentNode.gridPosition;

        Node validNeighbourNode;

        // 遍及所有方向
        for (int i = -1; i <= 1; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                if (i == 0 && j == 0)
                    continue;

                validNeighbourNode = GetValidNodeNeighbour(currentNodeGridPosition.x + i, currentNodeGridPosition.y + j,
                    gridNodes, closedNodeHashSet, instantiatedRoom);

                if (validNeighbourNode != null)
                {
                    // 计算邻居的新 gcost
                    int newCostToNeighbour;

                    // 获得移动罚款
                    // 不可行走的路径的值为 0。默认移动惩罚设置在
                    // 设置并应用于其他网格方块。
                    int movementPenaltyForGridSpace =
                        instantiatedRoom.aStarMovementPenalty[validNeighbourNode.gridPosition.x,
                            validNeighbourNode.gridPosition.y];

                    newCostToNeighbour = currentNode.gCost + GetDistance(currentNode, validNeighbourNode);

                    bool isValidNeighbourNodeInOpenList = openNodeList.Contains(validNeighbourNode);

                    if (newCostToNeighbour < validNeighbourNode.gCost || !isValidNeighbourNodeInOpenList)
                    {
                        validNeighbourNode.gCost = newCostToNeighbour;
                        validNeighbourNode.hCost = GetDistance(validNeighbourNode, targetNode);
                        validNeighbourNode.parentNode = currentNode;

                        if (!isValidNeighbourNodeInOpenList)
                        {
                            openNodeList.Add(validNeighbourNode);
                        }
                    }
                }
            }
        }
    }

    /// <summary>
    /// 返回 nodeA 和 nodeB 之间的距离 int
    /// </summary>
    private static int GetDistance(Node nodeA, Node nodeB)
    {
        int dstX = Mathf.Abs(nodeA.gridPosition.x - nodeB.gridPosition.x);
        int dstY = Mathf.Abs(nodeA.gridPosition.y - nodeB.gridPosition.y);

        if (dstX > dstY)
            return
                14 * dstY + 10 *
                (dstX - dstY); // 使用 10 代替 1,14 是毕达哥拉斯近似 SQRT（10*10 + 10*10） - 避免使用浮点数
        return 14 * dstX + 10 * (dstY - dstX);
    }

    /// <summary>
    /// 使用 neighboutNodeXPosition 和 neighbourNodeYPosition 评估相邻节点
    /// 指定了 gridNodes、closedNodeHashSet 和实例化的 room。 如果节点无效，则返回 null
    /// </summary>
    private static Node GetValidNodeNeighbour(int neighbourNodeXPosition, int neighbourNodeYPosition,
        GridNodes gridNodes, HashSet<Node> closedNodeHashSet, InstantiatedRoom instantiatedRoom)
    {
        // 如果邻居节点位置超出网格，则返回 null
        if (neighbourNodeXPosition >=
            instantiatedRoom.room.templateUpperBounds.x - instantiatedRoom.room.templateLowerBounds.x ||
            neighbourNodeXPosition < 0 ||
            neighbourNodeYPosition >= instantiatedRoom.room.templateUpperBounds.y -
            instantiatedRoom.room.templateLowerBounds.y || neighbourNodeYPosition < 0)
        {
            return null;
        }

        // 获取邻居节点
        Node neighbourNode = gridNodes.GetGridNode(neighbourNodeXPosition, neighbourNodeYPosition);
        
        // 检查该位置是否有障碍物
        int movementPenaltyForGridSpace = instantiatedRoom.aStarMovementPenalty[neighbourNodeXPosition, neighbourNodeYPosition];
        
        // 检查该位置是否有可移动的障碍物
        int itemObstacleForGridSpace = instantiatedRoom.aStarItemObstacles[neighbourNodeXPosition, neighbourNodeYPosition];

        // 如果邻居是障碍物或邻居在已关闭的列表中，则跳过
        if (movementPenaltyForGridSpace == 0 || itemObstacleForGridSpace == 0 || closedNodeHashSet.Contains(neighbourNode))
        {
            return null;
        }
        else
        {
            return neighbourNode;
        }
    }
}